package cn.wy.day01;

/*
* 题目：两数之和
* 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
* 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
*
* 示例:
* 给定 nums = [2, 7, 11, 15], target = 9
* 因为 nums[0] + nums[1] = 2 + 7 = 9
* 所以返回 [0, 1]
*
* Related Topics 数组 哈希表
 * */

import cn.wy.util.RunTimeUtils;
import cn.wy.util.StringArrayUtils;

import java.util.HashMap;
import java.util.Scanner;

public class Solution1 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String numsStr = sc.nextLine();//接受用户键盘输入numsStr
        int[] nums = StringArrayUtils.stringToArray(numsStr); //将输入的字符串转换为整数数组

        int target = sc.nextInt();

        long startTime = RunTimeUtils.getStartTime(); //开始时间

        int[] results = method1(nums, target); //方法一
//        int[] results = method2(nums, target); //方法二

        long endTime = RunTimeUtils.getEndTime();//结束时间
        System.out.println(RunTimeUtils.getRunTime(startTime,endTime));

        String result = StringArrayUtils.arrayToString(results);
        System.out.println(result);

    }




    /*
     * 方法1：双层循环数组暴力破解法
     * 时间复杂度：n-1 + n-2 + n-3 + n-4 + .....+ 1 = (1+n-1)*(n-1)/2 = (n^2 - n)/2 ≈ n^2
     * 空间复杂度：flag + i + j + result = 1+1+1+2 = 5
     * */
    public static int[] method1(int[] nums, int target) {

        boolean flag = false; //true时，循环提前终止
        int[] results = new int[2];//存放找到的下标，因为每种输入只会对应一种答案，故这里的只申请2个空间
        for (int i = 0; i < nums.length - 1; i++) {

            if (flag == false) { //还未找到继续循环
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[i] + nums[j] == target) {  //满足条件
                        results[0] = i;
                        results[1] = j;
                        flag = true;   //找到结果，将条件设置为true
                        break;//跳出内存循环
                    }
                }
            } else {
                break; //已找到则跳出外层循环
            }
        }
        return results;
    }


    /*
    * 方法2：哈希表法     通过键值对映射减少循环次数
    * 时间复杂度：在不考虑hashmap的查值的算法基础上，该方法的时间复杂度 = n + n = 2n ≈ n
    * 空间复杂度：map.length + results.length + i = 2n + 2 + 1 = 2n + 3 ≈ n
    * */
    public static int[] method2(int[] nums, int target){
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] results = new int[2];
        //将整数数组转换为map集合
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],i);//键为整数数组的值，值为整数数组的下标
        }
        for (int i = 0; i < nums.length; i++) {
            int index = map.get(target- nums[i]);
            if(map.get(target- nums[i]) != null){
                results[0] = i;
                results[1] = index;
                break;
            }
        }
        return results;
    }

}



